package divideYvenceras;

public class SubcadenaSumaMaxima {

	/**
	 * MTP
	 * El problema del subvector de suma máxima consiste en encontrar un
	 * subvector de una determinada longitud m cuya suma sea máxima dentro de un
	 * vector de longitud n, con m≤n. Este problema se puede resolver aplicando
	 * la técnica de divide y vencerás, formando problemas cada vez más pequeños
	 * hasta alcanzar un caso base y posteriormente combinando las soluciones
	 * obtenidas. En concreto, la forma de aplicar el método algorítmico citado
	 * consiste en obtener los segmentos de suma máxima correspondientes a las
	 * mitades izquierda y derecha del vector y a la parte central para, una vez
	 * calculados, elegir el máximo de los tres. El algoritmo tiene un coste
	 * lineal respecto al tiempo.
	 * 
	 */
	
	static int subvectorSumaMaxFuerzaBruta(int[] a){
		int sumaMax = 0,sumaAct = 0;
		for(int i=0;i< a.length;i++)
			for(int j=i;j< a.length;j++){
				sumaAct = 0;
				for(int k=0; k<j;sumaAct+=a[k])
					if (sumaAct>sumaMax)
						sumaMax = sumaAct;
			}
		return sumaMax;
	}
	
	static int subvectorSumaMaxDivideVenceras(int[] a){
		int sumaMax = 0,sumaAct = 0, i = 0;
			for(int j=0;j< a.length;j++){
				sumaAct+=a[j];				
					if (sumaAct>sumaMax)
						sumaMax = sumaAct;
					else if (sumaAct <= 0){
						i = j + 1;
						sumaAct = 0;
					}
			}
		return sumaMax;
	}
	
	 /** @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int [] vector = {1,-1,2,-2};
		
		System.out.println("suma max "+subvectorSumaMaxDivideVenceras(vector));

	}

}
